package com.kenliang.algorithm.dateStructure;

/**
 * @author KenLiang
 * @description: 堆结构
 * 大根堆 小根堆 ,此实例为小根堆
 * 逻辑结构是是基于完全二叉树的
 * 物理存储结构基于数组(index 从0开始)
 * @date Created in 11:47 AM 2021/1/22.
 */
public class HeapStructure {
    private int[] heapArray = null;
    private int heapSize = 0;

    public HeapStructure(int capacity) {
        this.heapArray = new int[capacity];
    }

    public void add(int value) {
        heapSize++;
        if (heapSize > heapArray.length) {
            throw new ArrayIndexOutOfBoundsException();
        }
        heapArray[heapSize - 1] = value;
        this.heapInsert(heapSize - 1);
    }

    public int poll() {

        int value = heapArray[0];
        this.swap(heapArray, 0, heapSize - 1);
        heapSize--;
        this.heapify(0);
        return value;
    }

    /**
     * 新增加的值在index位置，新增值上浮，直到0位置或者值比父亲小，重新调整堆的数据，保证堆的正确性
     *
     * @author KenLiang
     * @date 2021/1/22 11:50 AM
     */
    private void heapInsert(int index) {
        //如果父比自身小，交换  （如果父和自身相等或大，则停止上浮）
        while (heapArray[index] < heapArray[(index - 1) / 2]) {
            this.swap(heapArray, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }

    }

    /**
     * 指定index值下沉，直到无子女或者值比左右孩子都大，重新调整堆的数据，保证堆的正确性
     *
     * @param
     * @author KenLiang
     * @date 2021/1/22 12:07 PM
     */
    private void heapify(int index) {
        int leftChildIndex = index * 2 + 1;
        //左孩子没有越界
        while (leftChildIndex < heapSize) {
            //左右孩子中值最小的索引值
            int smallestChildIndex = leftChildIndex + 1 < heapSize && heapArray[leftChildIndex + 1] < heapArray[leftChildIndex] ? leftChildIndex + 1 : leftChildIndex;
            //左右孩子和父中值最小的索引值
            smallestChildIndex = heapArray[smallestChildIndex] < heapArray[index] ? smallestChildIndex : index;
            //父，左右孩子最小值为父，不需要下沉了，下沉结束
            if (smallestChildIndex == index) {
                break;
            }
            this.swap(heapArray, smallestChildIndex, index);
            index = smallestChildIndex;
            leftChildIndex = index * 2 + 1;
        }
    }

    private void swap(int[] in, int a, int b) {

        int temp = in[b];
        in[b] = in[a];
        in[a] = temp;
        //a和b内存地址一样，出来的结果就变成0了
//        in[b] = in[a] ^ in[b];
//        in[a] = in[a] ^ in[b];
//        in[b] = in[a] ^ in[b];
    }


    public static void main(String[] args) {
        HeapStructure heapStructure = new HeapStructure(10);
        heapStructure.add(4);
        heapStructure.add(3);
        heapStructure.add(4);
        heapStructure.add(7);
        heapStructure.add(8);
        heapStructure.add(1);
        heapStructure.add(2);
        soutArray(heapStructure.heapArray, heapStructure.heapSize);
        System.out.println(heapStructure.poll());
        System.out.println(heapStructure.poll());
        System.out.println(heapStructure.poll());
        System.out.println(heapStructure.poll());
        System.out.println(heapStructure.poll());
        System.out.println(heapStructure.poll());
        System.out.println(heapStructure.poll());
    }

    public static void soutArray(int[] in, int size) {
        for (int i = 0; i < size; i++) {
            System.out.print(in[i]);
            System.out.print(",");
        }
        System.out.println("");
    }
}
